package question.solution34;

import question.SolutionTemplate;

public class Solution34 implements SolutionTemplate {

    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if(nums.length == 0){
            return result;
        }
        int pl = 0;
        int pr = nums.length-1;
        int mid;
        // 找左边界
        int leftEdge = -1;
        while(pl <= pr){
            mid = (pl + pr)/2;
            if(nums[mid] > target){
                pr = mid - 1;
            }else if(nums[mid] < target){
                pl = mid + 1;
            }else{
                if(mid - 1 <0 ||nums[mid-1] < target){
                    leftEdge = mid;
                    break;
                }
                pr = mid - 1;
            }
        }
        if(leftEdge == -1){
            return result;
        }
        // 找右边界
        pl = leftEdge;
        pr = nums.length-1;
        int rightEdge = -1;
        while(pl <= pr){
            mid = (pl + pr)/2;
            if(nums[mid] < target){
                pl = mid + 1;
            }else if(nums[mid] > target){
                pr = mid - 1;
            }else{
                if(mid + 1 > nums.length-1 ||nums[mid+1] > target){
                    rightEdge = mid;
                    break;
                }
                pl = mid + 1;
            }
        }
        result[0] = leftEdge;
        result[1] = rightEdge;
        return result;
    }
    public void test() {
        int[] nums = {5,7,7,8,8,10};
        int[] result = searchRange(nums, 8);

        int[] nums2 = {1};
        result = searchRange(nums2, 1);

        int[] nums3 = {1};
        result = searchRange(nums3, 0);
        return;
    }
}
